@Techreport{C12tech,
  AUTHOR =   {Peter {\v C}erno},
  TITLE =    {Clearing Restarting Automata and Grammatical Inference},
  INSTITUTION =  {Charles University, Faculty of Mathematics and Physics},
  YEAR =     {2012},
  ADDRESS =  {Prague},
  URL =      {http://popelka.ms.mff.cuni.cz/cerno/files/cerno_clra_and_gi.pdf},
  ABSTRACT = {Clearing and subword-clearing restarting automata are linguistically motivated 
              models of automata. We investigate the problem of grammatical inference for such
              automata based on the given set of positive and negative samples.
              We show that it is possible to identify these models in the limit. In this 
              way we can learn a large class of languages. On the other hand, we prove that 
              the task of finding a clearing restarting automaton consistent with a 
              given set of positive and negative samples is NP-hard, provided that we
              impose an upper bound on the width of its instructions.},
  KEYWORDS = {grammatical inference, clearing restarting automata, 
              subword-clearing restarting automata, formal languages},
}

@INPROCEEDINGS{CM09,
  AUTHOR =       {Peter {\v C}erno and Franti{\v s}ek Mr{\'a}z},
  TITLE =        {Clearing restarting automata},
  BOOKTITLE =    {Workshop on Non-Classical Models for Automata and Applications (NCMA)},
  YEAR =         {2009},
  editor =       {Henning Bordinh and Rudolf Freund and Markus Holzer and Martin Kutrib and Friedrich Otto},
  pages =        {77--90},
  publisher =    {{\"O}sterreichisches Computer Gesellschaft},
  series =       {books@ocg.at},
  volume =       256,
}

@Article{CM10,
  AUTHOR =   {Peter {\v C}erno and Franti{\v s}ek Mr{\'a}z},
  TITLE =    {Clearing Restarting Automata},
  JOURNAL =  {Fundamenta Informaticae},
  VOLUME =   {104},
  NUMBER =   {1},
  PAGES =    {17--54},
  YEAR =     {2010},
  DOI =      {DOI 10.3233/FI-2010-334},
  ABSTRACT = {Restarting automata were introduced as a model for analysis by reduction,
              which is a linguistically motivated method for checking correctness of a sentence.
              We propose a new restricted version of restarting automata called clearing restarting automata
              with a very simple definition but simultaneously with interesting properties with respect
              to their possible applications. The new model can be learned very efficiently from positive examples
              and its stronger version can be used to learn effectively a large class of languages. We relate
              the class of languages recognized by clearing restarting automata to the Chomsky hierarchy.},
}

@incollection {CM11,
   author = {Peter {\v C}erno and Franti{\v s}ek Mr{\'a}z},
   affiliation = {Department of Computer Science, Charles University, Faculty of Mathematics and Physics, Malostransk{\'e} n{\'a}m. 25, 118 00 PRAHA 1, Czech Republic},
   title = {Delta-Clearing Restarting Automata and CFL},
   booktitle = {Developments in Language Theory},
   series = {Lecture Notes in Computer Science},
   editor = {Mauri, Giancarlo and Leporati, Alberto},
   publisher = {Springer Berlin / Heidelberg},
   isbn = {},
   pages = {153-164},
   volume = {6795},
   abstract = {Delta-clearing restarting automata represent a new restricted model of restarting automata which,
               based on a limited context, can either delete a substring of the current content of its tape or
               replace a substring by a special auxiliary symbol Delta, which cannot be overwritten anymore,
               but it can be deleted later. The main result of this paper consists in the proving that beside
               their limited operations, Delta-clearing restarting automata recognize all context-free languages.},
   keywords = {analysis by reduction, context-free languages, Delta-clearing restarting automata, formal languages},
   url = {http://dx.doi.org/10.1007/978-3-642-22321-1_14},
   year = {2011}
}

@Techreport{CM11tech,
  AUTHOR =   {Peter {\v C}erno and Franti{\v s}ek Mr{\'a}z},
  TITLE =    {Delta-Clearing Restarting Automata and CFL},
  INSTITUTION =  {Charles University, Faculty of Mathematics and Physics},
  YEAR =     {2011},
  ADDRESS =  {Prague},
  URL =      {http://popelka.ms.mff.cuni.cz/cerno/files/cerno_mraz_dclra_and_cfl.pdf},
  ABSTRACT = {Delta-clearing restarting automata represent a new restricted model of restarting automata which,
              based on a limited context, can either delete a substring of the current content of its tape or
              replace a substring by a special auxiliary symbol $\Delta$, which cannot be overwritten anymore,
              but it can be deleted later. The main result of this paper consists in the proving that beside
              their limited operations, Delta-clearing restarting automata recognize all context-free languages.},
  KEYWORDS = {analysis by reduction, context-free languages, Delta-clearing restarting automata, formal languages},
}

@Book{HU69,
  author =       "John E. Hopcroft and J. D. Ullman",
  title =        "Formal Languages and their Relation to Automata",
  publisher =    "Addison-Wesley",
  address =      "Reading",
  year =         "1969",
  ISBN =         "0-201-02983-9",
  descriptor =   "Automat, Automatentheorie, {C}omsky-Hierarchie,
                 Endlicher Automat, Entscheidbarkeit, Formale Sprache,
                 Grammatik, Halteproblem, Kellerautomat, Kontextfrei,
                 Kontextsensitiv, Linear-beschraenkt, Sprache,
                 Sprachoperation, Turing Maschine",
  annote =       "1. Languages and their representations 2. Grammars 3.
                 Finite automata and regular grammars 4. Context-free
                 grammars 5. Pushdown automata 6. Turing machines 7.
                 Turing machines: The halting problem, type 0 languages
                 8. Linear bounded automata and context-sensitive
                 languages 9. Operations and languages 10. Time- and
                 tape-bounded turing machines 11. Time and space bounds
                 for recognizing context-free languages 12.
                 Deterministic pushdown automata 13. Stack automata 14.
                 Decidability",
}

@InProceedings{JMPV95,
  author =       "Petr Jan{\v c}ar and Franti{\v s}ek Mr{\'a}z and Martin Pl{\'a}tek and J{\"o}rg Vogel",
  title =        "Restarting Automata",
  series =       "LNCS",
  booktitle =    "FCT'95",
  editor =       "Horst Reichel",
  volume =       "965",
  publisher =    "Springer",
  pages =        "283--292",
  year =         "1995",
  month =        "August",
  address =      "Dresden, Germany",
  coden =        "LNCSD9",
  ISBN =         "0302-9743",
  bibdate =      "Sat May 11 13:45:32 MDT 1996",
}

@INCOLLECTION{O06,
  AUTHOR =       {Friedrich Otto},
  TITLE =        {Restarting automata},
  BOOKTITLE =    {Recent Advances in Formal Languages and Applications},
  PUBLISHER =    {Springer},
  YEAR =         {2006},
  editor =       {Zolt{\'a}n {\'E}sik and Carlos Mart{\'\i}n-Vide and Victor Mitrana},
  volume =       {25},
  series =       {Studies in Computational Intelligence},
  pages =        {269--303},
  address =      {Berlin},
  abstract =     {The restarting automaton was introduced by Jan{\v c}ar et al. in 1995 in
                  order to model the so-called ``analysis by
                  reduction,'' which is a technique used in
                  linguistics to analyse sentences of natural
                  languages that have a free word order. By now
                  there are many different models of restarting
                  automata, and their investigation has proved very
                  fruitful in that they offer an opportunity to
                  study the influence of various kinds of resources
                  on their expressive power. Here we introduce and
                  discuss the main variants of these automata, and
                  present the main results that have been obtained
                  until now. In particular, we investigate the
                  relationship of the language classes that are
                  defined through the various types of restarting
                  automata to the classes of the Chomsky hierarchy,
                  and we address some open problems.},
  keywords =     {restarting automata},
}
